package leetcode.editor.cn.dsa22_segmentTree;
//给你一个整数数组 target 和一个数组 initial ，initial 数组与 target 数组有同样的维度，且一开始全部为 0 。
//
// 请你返回从 initial 得到 target 的最少操作次数，每次操作需遵循以下规则： 
// 在 initial 中选择 任意 子数组，并将子数组中每个元素增加 1 。
// 答案保证在 32 位有符号整数以内。
//
// 示例 1： 
// 输入：target = [1,2,3,2,1]
//输出：3
//解释：我们需要至少 3 次操作从 intial 数组得到 target 数组。
//[0,0,0,0,0] 将下标为 0 到 4 的元素（包含二者）加 1 。
//[1,1,1,1,1] 将下标为 1 到 3 的元素（包含二者）加 1 。
//[1,2,2,2,1] 将下表为 2 的元素增加 1 。
//[1,2,3,2,1] 得到了目标数组。
// 
//
// 示例 2： 
// 输入：target = [3,1,1,2]
//输出：4
//解释：(initial)[0,0,0,0] -> [1,1,1,1] -> [1,1,1,2] -> [2,1,1,2] -> [3,1,1,2] (tar
//get) 。
// 
//
// 示例 3： 
// 输入：target = [3,1,5,4,2]
//输出：7
//解释：(initial)[0,0,0,0,0] -> [1,1,1,1,1] -> [2,1,1,1,1] -> [3,1,1,1,1] 
//                                  -> [3,1,2,2,2] -> [3,1,3,3,2] -> [3,1,4,4,2]
// -> [3,1,5,4,2] (target)。
// 
// 示例 4：
// 输入：target = [1,1,1,1]
//输出：1
//
// 提示：
// 1 <= target.length <= 10^5
// 1 <= target[i] <= 10^5 
// 
// Related Topics 线段树 
// 👍 23 👎 0

public class MinimumNumberOfIncrementsOnSubarraysToFormATargetArray1526 {
    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        class SegTree { // 定义线段树，采用数组存储
            int[] value, nums;
            int n; // 表示nums数组的长度
            SegTree(int n, int[] nums) {
                value = new int[4 * n];
                this.n = n;
                this.nums = nums;
                build(1, 0, n - 1); // 起始坐标从1开始
            }
            // pos表示 nums[left,right]最小值坐标在value中存储的位置
            void build(int pos, int left, int right) {
                if (left == right) {
                    value[pos] = left; // 存储原数组索引
                    return;
                }
                int mid = (left + right) / 2;
                build(2 * pos, left, mid); // 建立左子树
                build(2 * pos + 1, mid + 1, right); // 建立右子树
                int leftIndex = value[2 * pos];
                int rightIndex = value[2 * pos + 1];
                // 比较这两个索引位置的元素大小，存储的是较小值的索引
                value[pos] = nums[leftIndex] > nums[rightIndex] ? rightIndex : leftIndex;
            }
            // pos为nums[left,right]最小值的坐标在value中存储的位置
            int query(int pos, int left, int right, int qleft, int qright)  {
                // 递归出口：查询区间相等或者不存在
                if (qleft > qright) return -1;
                if (qleft == left && qright == right) return value[pos];
                int mid = (left + right) / 2;
                // 搜索左子树和右子树区间最小值的坐标
                int leftIndex = query(2 * pos, left, mid, qleft, Math.min(mid, qright));
                int rightIndex = query(2 * pos + 1, mid + 1, right, Math.max(mid+1, qleft), qright);
                if (leftIndex == -1) return rightIndex;
                if (rightIndex == -1) return leftIndex;
                return nums[leftIndex] > nums[rightIndex] ? rightIndex : leftIndex;
            }
            // 分别对左右子区间递归累加直至区间最小值，本题定制函数
            int rec(int last, int l, int r) {
                if (l > r) return 0; // 递归出口：搜索区间不存在
                // 获取当前区间最小值索引
                int min = query(1, 0, n - 1, l, r);
                // 总的次数 = 当前累加次数 + 左侧区间累加次数 + 右侧区间累加次数
                // last代表上一次累加后的值，当前节点应在上次基础值上继续累加
                return nums[min] - last + rec(nums[min], l, min - 1)
                        + rec(nums[min], min + 1, r);
            }
        }

        public int minNumberOperations(int[] target) {
            // 新建一棵线段树
            SegTree st = new SegTree(target.length, target);
            // 调用线段树求出目标值
            return st.rec(0, 0, target.length - 1);
        }
    }
    //leetcode submit region end(Prohibit modification and deletion)
}